package com.acme.HashMapInteger;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class IntHashMap implements Map<Integer, Integer> {
	private static final int DEFAULT_TABLE_SIZE = 128;
	private int tableSize;
	private int primeForHash2 = 127;
	private int size = 0;

	private int[] keys;
	private int[] values;

	public IntHashMap() {
		this(DEFAULT_TABLE_SIZE);
	}

	public IntHashMap(int tableSize) {
		this.tableSize = tableSize;
		this.keys = new int[tableSize];
		this.values = new int[tableSize];
		this.primeForHash2 = new BigInteger(Long.toString(tableSize / 2)).nextProbablePrime().intValue();
	}

	public int size() {
		return size;
	}

	public Integer get(int key) {
		int firstHash = -1;
		int h1 = hash1(key);
		int h2 = hash2(key);

		while ((keys[h1] != 0) && (keys[h1] != key) && (h1 != firstHash)) {
			if (firstHash == -1) {
				firstHash = h1;
			}
			h1 = (h1 + h2) % tableSize;
		}

		if ((keys[h1] == 0) || h1 == (firstHash)) {
			return null;
		}

		return values[h1];
	}

	public Integer put(int key, int value) {
		int slot = findEmptySlot(key);
		if (slot == -1) {
			rebuildHashMap();
			slot = findEmptySlot(key);
			if (slot == -1) {
				return null;
			}
		}
		keys[slot] = key;
		values[slot] = value;
		size++;

		return value;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void clear() {
		keys = new int[tableSize];
		values = new int[tableSize];
		size = 0;
	}

	private int findEmptySlot(int key) {
		int firstHash = -1;
		int h1 = hash1(key);
		int h2 = hash2(key);
		int probes = 0;
		
			
		while ((keys[h1] != 0) && (h1 != firstHash)) {
			if (firstHash == -1) {
				firstHash = h1;
			}
			probes++;
			h1 = (firstHash + probes * h2) % tableSize;
		}

		if (h1 == firstHash) {
			return -1;
		}
		return h1;
	}

	private void rebuildHashMap() {
		int oldTableSize = tableSize;
		int[] oldKeys = Arrays.copyOf(keys, tableSize);
		int[] oldValues = Arrays.copyOf(values, tableSize);
		tableSize *= 2;
		primeForHash2 = new BigInteger(Long.toString(tableSize / 2)).nextProbablePrime().intValue();
		keys = new int[tableSize];
		values = new int[tableSize];
		size = 0;

		for (int i = 0; i < oldTableSize; i++) {
			if (oldKeys[i] > 0) {
				put(oldKeys[i], oldValues[i]);
			}
		}
	}

	private int hash1(int key) {
		/* Robert Jenkins' 32 bit Mix Function */
		key += (key << 12);
		key ^= (key >> 22); 
		key += (key << 4); 
		key ^= (key >> 9); 
		key += (key << 10); 
		key ^= (key >> 2); 
		key += (key << 7);
		key ^= (key >> 12);

		return key % this.tableSize;
	}

	private int hash2(int key) {
		return primeForHash2 - (key % primeForHash2);
//		return 1;
	}

	public int[] getKeys() {
		return keys;
	}

	public int[] getValues() {
		return values;
	}

	public int getTableSize() {
		return tableSize;
	}

	public boolean containsKey(Object key) {
		return false;
	}

	public boolean containsValue(Object value) {
		return false;
	}

	public Integer get(Object key) {
		return get((int) (Integer)key);
	}

	public Integer put(Integer key, Integer value) {
		return put((int) key, (int) value);
	}

	public Integer remove(Object key) {
		return null;
	}

	public void putAll(Map m) {

	}

	public Set keySet() {
		return null;
	}

	public Collection values() {
		return null;
	}

	public Set entrySet() {
		return null;
	}
}
